package src.leetcode.dp.hard_0188;

public class maxProfit {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxProfit(2,new int[]{3,2,6,5,0,3}));
    }
}

class Solution {
    public int maxProfit(int k, int[] prices) {
        int [][]dp = new int[prices.length][2 * k + 1];

        for(int i = 1; i < 2 * k + 1;i += 2){
            dp[0][i] = -prices[0];
        }

        for(int i = 1; i < prices.length; i++){
            for(int j = 1; j < 2 * k + 1; j++) {
                if(j % 2 == 1){
                    // 奇数，代表买入
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                }else{
                    // 偶数，代表卖出
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                }
            }
        }

        return dp[prices.length - 1][2 * k];
    }
}